package com.ting.test.algorithms.贪心算法.居民街道装灯问题;

/**
 * 给定一个字符串str，只由‘X’和‘.’两种字符构成。
 * ‘X’表示墙，不能放灯，也不需要点亮
 * ‘.’表示居民点，可以放灯，需要点亮
 * 如果灯放在i位置，可以让i-1，i和i+1三个位置被点亮
 * 返回如果点亮str中所有需要点亮的位置，至少需要几盏灯
 * 分析，
 * 1. 注意 题意是要要求必须所有的.位置必须装灯或者至少能亮
 * 假设当前位置 i:
 * 1. 如果i位置是X，直接跳过，不装灯
 * 1. 如果i+1位置是X 也直接跳过
 * 2. 如果i+1位置是.
 * <p>
 * <p>
 * 2. 如果i位置是. 则表示需要装灯，或者至少i+1位置需要装灯
 * 1. 如果I+1位置是X  则i位置必须装灯
 * 2. 如果i+1位置是.则i+1位置需要装灯 i位置不需要装灯也能亮
 * 1. 如果i+2位置是X 则灯装在I+1或者位置都可以
 * 2. 如果i+2位置是. 则等需要装在I+1位置
 */
public class 街道装灯 {
    public static void main(String[] args) {
        String[] arr = new String[]{"X", ".", "X", ".", "X", ".", "X","."};
        int count = fun(arr);
        System.out.println(count);
    }

    private static int fun(String[] arr) {

        int i = 0;
        int count = 0;
        while (i < arr.length) {
            if (arr[i].equalsIgnoreCase("X")) {
                i++;
            } else {
                count++;
                if (i + 1 == arr.length) {//表示到头了
                    return count;
                }

                if (arr[i + 1].equalsIgnoreCase("X")) {
                    i++;
                } else {
                    i = i + 2;
                }
            }
        }
        return count;
    }
}
